package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
 */
public class Title309 {

    /**
     * 状态：0 不操作、1 买入股票状态、2 卖出（度过冷冻期）、3 今天卖出、4 今天冷冻期(状态不可持续）
     * dp[i][j]表示：第i天保持j状态时有多少钱
     * 递推公式：
     * 1、买入股票：
     *    以前没买                          -prices[i]
     *    以前买过：                        dp[i-1][1]
     *    今天买：
     *        前几天卖出过（且度过冷冻期）  dp[i-1][2] - prices[i]
     *        上一天为冷冻期                dp[i-1][4] - prices[i]
     *    dp[i][1] = Math.max(- prices[i], dp[i-1][1], Math.max(dp[i-1][2],dp[i-1][4]) - prices[i])
     * 2、卖出（度过冷冻期）
     *    以前就卖出度过冷冻期了           dp[i-1][2]
     *    以前卖，昨天是冷冻期             dp[i-1][4]
     *    dp[i][2] = Math.max(dp[i-1][2], dp[i-1][4])
     * 3、今天卖出
     *    以前买过                         dp[i-1][1] + prices[i]
     *    dp[i][3] = dp[i-1][1] + prices[i]
     * 4、今天冷冻期
     *    昨天必定为卖过                   dp[i-1][3]
     *    dp[i][4] = dp[i-1][3]
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][5];
        //初始化
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][1] = Math.max(Math.max(-prices[i], dp[i - 1][1]), Math.max(dp[i - 1][2], dp[i - 1][4]) - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][4]);
            dp[i][3] = dp[i - 1][1] + prices[i];
            dp[i][4] = dp[i - 1][3];
        }
        return Math.max(dp[prices.length - 1][2], Math.max(dp[prices.length - 1][3], dp[prices.length - 1][4]));
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,0,2};
        maxProfit(arr);
    }
}
